Path planning or path finding methods are used in many applications, for instance, in robotics, computer games, graphics, vision and imaging. Various path planning or path finding methods have been reported in the art, in particular A*, and Fast-marching methods. Shortest path algorithms on graphs, for example Dijkstra's algorithm, are described in Cormen, Leiserson and Rivest, “Introduction to Algorithms”, McGraw-Hill.
A* is described in N. Nilsson, “Problem-Solving Methods in Artificial Intelligence”, McGraw-Hill, N.Y., 1971. Fast-marching methods are described in J. A. Sethian, “A fast marching level set method for monotonically advancing fronts”, Nat. Acad. Sci. 93(4) (1996) 1591-1595; and in Sethian, “Fast marching methods”, SIAM Rev. 41 (2) (1999) 199-235; and in http://math.berkeley.edu/˜sethian, and in a book by Sethian “Level-sets method and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision and Material Sciences”, Cambridge University Press, 1999. Path planning methods are describes in United States Patents: U.S. Pat. No. 6,324,478; U.S. Pat. No. 6,604,005 and U.S. Pat. No. 6,496,188.
A* and Fast-Marching are compared in P. Melchior et al. “Consideration of obstacle danger level in path planning using A* and Fast-Marching optimization: comparative study”, Signal Processing, v. 83 n. 11 p. 2387-2396, November 2003; and in Livingstone et al. “Fast marching and fast driving: combining off-line search and reactive A.I.”, 4th International Conference on Intelligent Games and Simulation (GAME-ON 2003), November 2003, UK. The paper by Melchior relates to a mobile robot application. The paper by Livingstone relates to a video game.
A* usually solves a continuous path problems by converting the problem to a discrete problem defined by a graph and then finding a solution on the graph. Fast-Marching solves continuous path problems by using grid based numerical approximations to the underlying problem.
Finding paths in 3D images using Fast Marching is described in T. Deschamps and L. D. Cohen “Fast Extraction of Minimal paths in 3D images and application to virtual endoscopy”, Medical Image Analysis, Vol. 5, Issue 4, December 2001.
The disclosures of all of the above referenced patents and publications are incorporated herein by reference, in their entirety.